Realization of novel molecular function requires the ability to alter molecular complex formation. Enzymatic function can be altered by changing enzyme-substrate interactions via modification of an enzyme's active site. We propose a new algorithm for protein redesign, which combines a statistical mechanics-derived ensemble-based approach to computing the binding constant with the speed and completeness of a branch-and-bound pruning algorithm. In addition, we propose an efficient, deterministic approximation algorithm, capable of approximating our scoring function to arbitrary precision. Our ensemble-based algorithm, which flexibly models both protein and ligand using rotamer-based partition functions, has application in enzyme redesign, the prediction of protein-ligand binding, and computer-aided drug design. In preliminary studies, we redesigned the phenylalanine-specific adenylation domain of the non-ribosomal peptide synthetase Gramicidin Synthetase A (NRPS GrsA-PheA). Ensemble scoring, using a rotameric approximation to the partition functions of the bound and unbound states for GrsA-PheA, was used to switch the enzyme specificity toward leucine (Leu) and tyrosine (Tyr), using novel active site sequences computationally predicted by searching through the space of possible active site mutations. The top-scoring in silico mutants were created in vitro, and binding and catalytic activity were measured. Several of the top-ranked mutations exhibit the desired change in specificity from Phe to Leu or Tyr. When considering protein flexibility and molecular ensembles for protein design, a major challenge has been the development of ensemble-based redesign algorithms that efficiently prune mutations and conformations. The proposed K* ("K-star") method generalizes Boltzmann-based scoring to ensembles and applies the result to protein design. K prunes the vast majority of conformations, thereby reducing execution time and making a mutation search that considers both ligand and protein flexibility computationally feasible. In addition to redesigning PheA, the K algorithm will be used to reprogram the specificity of other NRPS domains, whose products include natural antibiotics, antifungals, antivirals, immuno- suppressants, and antineoplastics. We will also use our algorithms to redesign two restriction endonucleases (REs), and will apply K to design peptide inhibitors for the CAL (Cystic fibrosis transmembrane conductance regulator Associated Ligand) PDZ domain. Our algorithms will predict NRPS and RE mutants with putative novel function, and we will create the mutant proteins, and test our predictions by using biochemical activity assays and determining new crystal structures. We will test the predicted CAL-binding peptides both in vitro and in vivo. Project Narrative: Enzyme redesign provides a good test of our understanding of proteins. The long-term goal of our research is to develop novel algorithms to plan structure-based site-directed mutations to a protein's active site in order to modify its function. We will develop general planning software that can reprogram the specificity of many proteins, including NRPS domains, whose products include natural antibiotics, antifungals, antivirals, immuno- suppressants, and antineoplastics. These engineered enzymes should enable combinatorial biosynthesis of novel pharmacologically-active compounds, yielding new leads for drug design. The proposed application of our algorithms to restriction endonucleases and the CAL PDZ domain could lead to (respectively) biotechnology advances and novel therapeutic interventions for cystic fibrosis.